Prior art land vehicle navigation apparatuses for planning a new or recovery route after departure from the original route use several different methods of recovery route planning. The first and most simple method is to simply advise the user he is off-route but provide no advice on how to get back to the original route nor provide information on how to get from the current land vehicle location to the original destination. A second slightly more sophisticated method is that the system advises the user that she is off-route and then waits for the user to make some input into the system to initiate recovery, such as requesting the user to press a "replan" button. In addition, the user could choose to cancel the route or drive without the use of the navigation apparatus. If the user were to return to the planned route at some point the navigation apparatus would detect this and resume providing route guidance. As those skilled in the art will realize, requiring user input may be difficult to perform while driving.
A third still more sophisticated prior art method detects the off-route condition and automatically replans an entirely new route from the current vehicle location to the original destination. A fourth method automatically replans a recovery route from the current vehicle location back to the point of route departure.
As can be seen the first and second methods of the prior art are simple and do not automatically plan a recovery route but instead either give no advice or wait for user input before taking any recovery action. The third and fourth methods while providing for automatic recovery route planning either take substantial amount of time or plan significantly inconvenient recovery routes.
For example, the third method described above replans an entirely new route from the current vehicle location to the original destination and even given a very fast route planner a land vehicle navigation system can still take over 30 seconds to plan a new route. In this amount of time the user may have already passed a necessary turn-off or fork in the road along the newly planned route. Therefore, there is a need to have a route planner system automatically plan a recovery route in a very short amount of time, after detecting a route departure to ensure that the user does not miss any necessary turns. This is particularly true because the route departure occurs while driving and the vehicle is therefore in motion at the time that recovery guidance is needed. A lag on the order of thirty seconds is simply too long to wait while a vehicle is in motion and a driver is waiting for recovery instructions. If the driver is in unfamiliar territory he would not necessarily know where to go while waiting for a recovery route to be planned and, in fact, may drive to a point off the replanned route thereby requiring another entirely new route to be planned. Obviously , it is also undesirable for the user to be required to stop the car and wait for the route plan to be completed. This would require pulling off on the shoulder of the road or into a parking lot which may be impractical, dangerous, or illegal.
The principal drawback of the fourth approach is that it tends to give a non-optimal route and often requires a lot of backtracking to get back to the point of route departure. This results in a loss of time and an unnecessary amount of driving. For example, if a driver took the wrong exit from a highway, the point of route departure is the segment of highway fight before the exit. To return to this segment may require several miles of driving back in the direction of the trip origin to get back on the highway. Using this system the user is guided in the direction back to the point from which he left even though there may be an entrance directly ahead that puts him back on the correct highway and carries the user towards his intended destination.